#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <math.h>
using namespace std;

struct arr
{
	int s;
	int e;
	int num;
	arr(){s=e=num=0;};
};

vector<int> place[1000010];//  num, idx
vector<arr> ans;//down left     num
int res;
int a[1000010]={};
int maxnum;

bool check(arr x,arr y)
{
	if(x.s<y.s&&x.e>y.e&&y.e-y.s==1) return 1;
	else if(x.s>y.s&&x.e<y.e&&x.e-x.s==1) return 1;
	else if(x.e < y.s) return 1;
	else if(y.e < x.s) return 1;
	else if(fabs(y.e-x.s)==1) return 1;
	else if(fabs(x.e-y.s)==1) return 1;
	else return 0;
}

int main()
{
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	
	int T;
	cin >> T;
	while(T--)
	{
		for(int i = 0;i <= maxnum;i++) place[i].resize(0);
		ans.resize(0);
//		cout << "--" << ans.size() << endl;
		memset(a,0,sizeof(a));
		res=0;
		int n;
		cin >> n;
		maxnum=0;
		for(int i =1;i<=n;i++)
		{
			cin >> a[i];
			maxnum=max(maxnum,a[i]);
		}
		for(int i =1;i<=n;i++)
		{
			place[a[i]].push_back(i);
		}
		for(int i =maxnum;i>=0;i--)
		{
			if(place[i].size()>1)
			{
				if((int)ans.size()==0)
				{
					for(int j =0;j<(int)place[i].size()-1;j++)
					{
						arr narr;
						narr.s=place[i][j];
						narr.e=place[i][j+1];
						narr.num=i;
						ans.push_back(narr);
					}
				}
				else
				{
					for(int j =0;j<(int)place[i].size()-1;j++)
					{
						arr narr;
						narr.s=place[i][j];
						narr.e=place[i][j+1];
						narr.num=i;
						int flg=1;
						for(int k = 0;k < (int)ans.size();k++)
						{
							arr g=ans[k];
							if(!check(narr,g))
							{
								flg=0;
								break;
							}
						}
						if(flg)
						{
							ans.push_back(narr);
						}
					}
				}
			}
		}
		for(int i = 0;i<(int)ans.size();i++)
		{
			res+=ans[i].num;
//			cout << ans[i].s << " " << ans[i].e << " " << ans[i].num << " " << endl; 
		}
		cout << res << endl;
	}
	
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
